package cn.qyd.leecode;

import java.util.*;

/**
 * @author 邱运铎
 * 先找 节点0 所有的子节点，然后将节点0 添加到他的所子节点的父节点集合中 result[子节点].add(节点0)
 * 一次类推 n-1 节点
 * 深度搜索 和 广度搜索 都需要考虑重复访问问题
 * 所以添加了visit数组控制当前节点是否已经访问过
 * 访问标识的值随着 节点的值增大而增大，这样保证一个访问标识数组即可，所以设置成int类型
 * @date 2024-04-04 22:42
 */
class Graph01 {
    public static void main(String[] args) {
        Graph01 graph01 = new Graph01();
        int n = 8;
        int[][] edges = new int[][]{{0,3},{0,4},{1,3},{2,4},{2,7},{3,5},{3,6},{3,7},{4,6}};
        List<List<Integer>> ancestors = graph01.getAncestors(n, edges);
        System.out.println(ancestors);
    }
    public List<List<Integer>> getAncestors(int n, int[][] edges) {
        List<Integer>[] toFroms = new List[n];
        Arrays.setAll(toFroms, item -> new ArrayList<>());

        for (int[] edge : edges) {
            toFroms[edge[0]].add(edge[1]);
        }

        List<Integer>[] results = new List[n];
        Arrays.setAll(results, item -> new ArrayList<>());
        int[] visit = new int[n];
        Arrays.fill(visit, -1);
        Queue<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            for (Integer son : toFroms[i]) {
                queue.offer(son);
            }

            while (!queue.isEmpty()) {
                Integer cur = queue.poll();
                if (visit[cur] != i) {
                    visit[cur] = i;
                    results[cur].add(i);
                    for (Integer son : toFroms[cur]) {
                        queue.offer(son);
                    }
                }
            }
        }


        return Arrays.asList(results);

    }

}
